
public class QuickSort{

	  /*function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      create empty lists 'less' and 'greater'
      select and remove a pivot value 'pivot' from 'array'
      for each 'x' in 'array'
      
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), 'pivot', quicksort('greater'))*/
	static long counter;
	
	public static void sort (Comparable[] array){
		counter = 0;
		sort(array, 0, array.length-1);
		System.out.println("Quicksort resolved in " + counter + "steps" );
		
		
		
		
	}
	
	private static void sort(Comparable[] array, int linkerIndex, int rechterIndex ){
		
		if(linkerIndex < rechterIndex){
			int pivotIndex = verdeel(array, linkerIndex, rechterIndex, linkerIndex + (rechterIndex-linkerIndex)/2);
			
			sort(array, linkerIndex, pivotIndex - 1);
			sort(array, pivotIndex + 1, rechterIndex);

			
			
		}
				
	}

	private static int verdeel(Comparable[] array, int linkerIndex, int rechterIndex, int pivotIndex) {
		
		   /*// left is the index of the leftmost element of the array
		   // right is the index of the rightmost element of the array (inclusive)
		   //   number of elements in subarray = right-left+1
		   function partition(array, 'left', 'right', 'pivotIndex')
		      'pivotValue' := array['pivotIndex']
		      swap array['pivotIndex'] and array['right']  // Move pivot to end
		      'storeIndex' := 'left'
		      for 'i' from 'left' to 'right' - 1  // left ≤ i < right
		          if array['i'] < 'pivotValue'
		              swap array['i'] and array['storeIndex']
		              'storeIndex' := 'storeIndex' + 1
		      swap array['storeIndex'] and array['right']  // Move pivot to its final place
		      return 'storeIndex'*/
		
		Comparable c = array[pivotIndex];
		verruil(array, pivotIndex, rechterIndex);
		int locatie = linkerIndex;
		Comparable s = null;
		for(int i = linkerIndex; i < rechterIndex; i++){
			if(c.compareTo(array[i]) == 1){
				 verruil(array, i, locatie);
				 locatie++;
			}
			counter++;
		}
		verruil(array, locatie, rechterIndex);
		
		
		
		return locatie;
	}
	
	static void verruil(Object[] array, int index1, int index2){
		Object s = array[index1];
		array[index1] = array[index2];
		array[index2] = s;
	}
	
}
